package com.abel.day0304;

import com.abel.day0301.TreeNode;

import java.util.*;

/**
 * @author xiachao
 * @date 2019/3/4
 */
public class Solution {

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

        ArrayList<TreeNode> arrayList = new ArrayList<TreeNode>();
        ArrayList<Integer> ret = new ArrayList();
        if(root == null){
            return ret;
        }
        int index = 0;
        arrayList.add(root);
        while (root.left!=null || root.right!=null){
            if(root.left!=null){
                arrayList.add(root.left);
            }
            if(root.right!=null){
                arrayList.add(root.right);
            }
            root = arrayList.get(++index);
        }
        for(TreeNode n : arrayList){
            ret.add(n.val);
        }
        return ret;
    }

    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0){
            return false;
        }
        return verify(sequence);
    }

    public boolean verify(int [] sequence){
        int len = sequence.length;
        if(len <= 1){
            return true;
        }
        int root = sequence[len-1];
        int mid = -1;
        for(int i=0;i<len-1;i++){
            if(sequence[i]>root){
                mid = i;
                break;
            }
        }
        if(mid == -1){
            return true;
        }
        for(int i=mid+1;i<len;i++){
            if(sequence[i]<root){
                return false;
            }
        }
        int [] arr1 = new int[mid];
        int [] arr2 = new int[len - mid - 1];
        for(int i=0;i<mid;i++) arr1[i] = sequence[i];
        for(int i=0;i<len-mid-1;i++) arr2[i] = sequence[mid + i];
        return verify(arr1) && verify(arr2);
    }


    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if(root == null){
            return new ArrayList<ArrayList<Integer>>();
        }
        return null;
    }

    public ArrayList<Integer> dfs(TreeNode root, int target, int cur, ArrayList<Integer> arr){
        if(cur == target){
            return arr;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if(left != null){
            arr.add(left.val);
            dfs(left, target, cur+left.val, arr);
            arr.remove(arr.size()-1);
        }
        return null;
    }

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> ret = new ArrayList<String>();
        if(str == null || "".equals(str)){
            return ret;
        }
        int [] arr = new int[str.length()];
        for(int i=0;i<str.length();i++){
            arr[i] = -1;
        }
        dfs(str, arr, 0, ret);

//        Collections.sort(ret, new Comparator<String>() {
//            public int compare(String o1, String o2) {
//                return o1.compareTo(o2);
//            }
//        });

        return ret;
    }

    public void dfs(String str, int [] arr, int cur, ArrayList<String> ret){
        if(cur == str.length()){
            String t = "";
            for(int i=0;i<cur;i++){
                t+=str.charAt(arr[i]);
            }
            if(!ret.contains(t)){
                ret.add(t);
            }
            return;
        }
        for(int i=0;i<str.length();i++){
            boolean ok = true;
            for(int j=0;j<=cur;j++){
                if(arr[j]==i){
                    ok = false;
                    break;
                }
            }
            if(ok){
                arr[cur] = i;
                dfs(str, arr, cur+1, ret);
                arr[cur] = -1;
            }
        }
    }


    public static void main(String[] args) {

        int [] arr = {1,2,3,2,2,2,5,4,2};
        //System.out.println(new Solution().MoreThanHalfNum_Solution(arr));

//        String str = "abcd";
//        System.out.println(new Solution().Permutation(str));

//        int [] seq = {5,4,3,2,1};
//        System.out.println(new Solution().VerifySquenceOfBST(seq));

//        TreeNode n1 = new TreeNode(8);
//        TreeNode n2 = new TreeNode(7);
//        TreeNode n3 = new TreeNode(6);
//        TreeNode n4 = new TreeNode(5);
//        TreeNode n5 = new TreeNode(4);
//
//        n1.left = n2;
//        n2.right = n3;
//        n3.left = n4;
//        n4.right = n5;
//
//        System.out.println(new Solution().PrintFromTopToBottom(n1));
    }
}

